package J.算法.动态规划;

import java.util.HashMap;
import java.util.Map;

public class _70爬楼梯 {

    /**
     * 递归法：
     * @param n
     * @return
     */
    Map<Integer,Integer> map = new HashMap<>();
    public int climbStairs(int n) {
        if (n<3){
            return n;
        }

        if (map.containsKey(n)){
            return map.get(n);
        }

        int n1 = climbStairs(n-1);
        map.put(n-1,n1);
        int n2 = climbStairs(n-2);
        map.put(n-2,n2);

        int res = n1+n2;
        map.put(n,res);
        return res;

    }

    /**
     * 动态规划 迭代
     * --好空间
     * 将dp数组换成dp map
     *
     */
    public int climbStairs1(int n){

        map.put(0,1);
        map.put(1,1);

        int count = 2;
        while (map.size()< n+1){
            map.put(count++,map.get(count-1)+map.get(count-2));
        }

        return map.get(n);
    }

    /**
     * 动态规划 迭代
     * 优化：只用两个变量存前两个状态的结果
     * 将dp数组换成dp map
     *
     */
    public int climbStairs2(int n){
        if (n<2){
            return n;
        }

        int prev = 1;
        int cur =1;
        int temp=0;

        for (int i = 2; i < n+1; i++) {
             temp = cur;
            cur = prev+cur;
            prev = temp;
        }


        return cur;

    }



}
